/**
Copyright (c) 2013 cnova

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
*/

library CollectionImplArray requires Collection

    //! textmacro define_arrayset takes S, STRUCTNAME
    
    private struct $STRUCTNAME$Node
        integer next 
        integer prev
        integer data
    endstruct
    private struct $STRUCTNAME$SlowIterator extends Iterator
        private $STRUCTNAME$Node curr
        static method create takes $STRUCTNAME$Node first, integer s returns thistype
            local thistype this = .allocate()
            set .curr = first
            set .end = .curr == 0
            return this
        endmethod
        implement IteratorModule
    endstruct

    $S$ struct $STRUCTNAME$Iterator
        private static integer next_index = 1
        $STRUCTNAME$Node curr
        readonly boolean end
        static method create takes $STRUCTNAME$Node first, integer s returns thistype
            local thistype this = thistype.next_index
            set thistype.next_index = thistype.next_index + 1
            if thistype.next_index > 8100 then
                set thistype.next_index = 1
            endif
            set .curr = first
            set .end = .curr == 0
            return this
        endmethod
        implement IteratorModule
    endstruct
    
    $S$ struct $STRUCTNAME$ extends Collection
        private $STRUCTNAME$Node first
        private $STRUCTNAME$Node last
        readonly integer size
        
        private static integer destroying
        
        method iterator takes nothing returns Iterator
            return $STRUCTNAME$SlowIterator.create(.first, .size)
        endmethod
        method fastIterator takes nothing returns $STRUCTNAME$Iterator
            return $STRUCTNAME$Iterator.create(.first, .size)
        endmethod
        
        method containsBy takes integer i, CompareFunction f returns integer
            local $STRUCTNAME$Node curr = .first
            local integer rval
            loop
                exitwhen curr == 0
                if f.evaluate(i, curr) then
                    return curr.data
                endif
                set curr = curr.next
            endloop
            return 0
        endmethod
        
        method removeBy takes integer i, CompareFunction f returns integer
            local $STRUCTNAME$Node curr = .first
            local integer rval
            local $STRUCTNAME$Node rprev
            local $STRUCTNAME$Node rnext
            loop
                exitwhen curr == 0
                if f.evaluate(i, curr) then
                    set rval = curr.data
                    if curr == .last then
                        set .last = curr.prev
                    elseif curr == .first then
                        set .first = curr.next
                    else
                        set rprev = curr.prev
                        set rnext = curr.next
                        set rprev.next = rnext
                        set rnext.prev = rprev
                    endif 
                    set .size = .size - 1
                    return rval
                endif
                set curr = curr.next
            endloop
            return 0
        endmethod
        
        method addAll takes Collection c returns nothing
            local Iterator it = c.iterator()
            loop
                exitwhen it.end
                call .add(it.next())
            endloop
        endmethod 

        method clear takes nothing returns nothing
            local $STRUCTNAME$Node toDestroy = .first
            local $STRUCTNAME$Node next = .first.next
            set .size = 0
            loop
                exitwhen next == 0 
                call toDestroy.destroy()
                set toDestroy = next
                set next = next.next
            endloop
            set .first = 0
            set .last = 0
        endmethod
        method contains takes integer i returns boolean
            return HaveSavedInteger(thistype.containsTable, this, i)
        endmethod
        method add takes integer i returns boolean
            local $STRUCTNAME$Node node 
            if .contains(i) then
                return false
            endif
            set node = $STRUCTNAME$Node.create()
            if .first == 0 then
                set .first = node
                set .last = node
            else
                set .last.next = node
                set node.prev = .last
                set .last = node
            endif
            set .size = .size + 1
            call SaveInteger(thistype.containsTable, this, i, node)
            return true
        endmethod
        method remove takes integer i returns boolean
            local $STRUCTNAME$Node node = LoadInteger(thistype.containsTable, this, i)
            local $STRUCTNAME$Node rprev
            local $STRUCTNAME$Node rnext
            if node == 0 then
                return false
            endif
            if node == .last then
                set .last = node.prev
            elseif node == .first then
                set .first = node.next
            else
                set rprev = node.prev
                set rnext = node.next
                set rprev.next = rnext
                set rnext.prev = rprev
            endif 
            set .size = .size - 1
            call SaveInteger(thistype.containsTable, this, i, 0) 
            call RemoveSavedInteger(thistype.containsTable, this, i) 
            call node.destroy()
            return true
        endmethod
        
        private static method cleanup takes $STRUCTNAME$Node node returns nothing
            local $STRUCTNAME$Node toDestroy = node
            local $STRUCTNAME$Node next = node.next
            local integer i = 0
            set .destroying = .destroying + 1
            loop
                exitwhen next == 0 
                call toDestroy.destroy()
                set toDestroy = next
                set next = next.next
                set i = i + 1
            endloop
            set .destroying = .destroying - 1
        endmethod
        method onDestroy takes nothing returns nothing
            set .size = 0
            call FlushChildHashtable(thistype.containsTable, this)
            call thistype.cleanup(.first)
        endmethod
    endstruct
    //! endtextmacro 

endlibrary